PittsburghV1, France, Analysis, bibRecord, 000152

Tight Bounds on Vertex Connectivity Under Vertex Sampling

Identifieur interne : 000152 ( France/Analysis ); précédent : 000151; suivant : 000153

Tight Bounds on Vertex Connectivity Under Vertex Sampling

Auteurs : Keren Censor-Hillel [Israël] ; Mohsen Ghaffari [États-Unis] ; George Giakkoupis [France] ; Bernhard Haeupler [États-Unis] ; Fabian Kuhn [Allemagne]

Source :

RBID : Hal:hal-01250519

Abstract

A fundamental result by Karger (SODA 1994) states that for any λ-edge-connected graph with n nodes, independently sampling each edge with probability p = Ω(log n/λ) results in a graph that has edge connectivity Ω(λp), with high probability. This paper proves the analogous result for vertex connectivity, when sampling vertices. We show that for any k-vertex-connected graph G with n nodes, if each node is independently sampled with probability p = Ω(log n/k), then the subgraph induced by the sampled nodes has vertex connectivity Ω(kp^2), with high probability. This bound improves upon the recent results of Censor-Hillel et al. (SODA 2014), and is existentially optimal.

Url:

https://hal.inria.fr/hal-01250519

DOI: 10.1137/1.9781611973730.133

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 000642
to stream Hal, to step Curation: 000642
to stream Hal, to step Checkpoint: 000173
to stream Main, to step Merge: 000212
to stream Main, to step Curation: 000212
to stream Main, to step Exploration: 000212
to stream France, to step Extraction: 000152

Links to Exploration step

Hal:hal-01250519

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Tight Bounds on Vertex Connectivity Under Vertex Sampling</title>
<author><name sortKey="Censor Hillel, Keren" sort="Censor Hillel, Keren" uniqKey="Censor Hillel K" first="Keren" last="Censor-Hillel">Keren Censor-Hillel</name>
<affiliation wicri:level="1"><hal:affiliation type="department" xml:id="struct-425640" status="VALID"><orgName>Department of Computer Science [Haifa]</orgName>
<date type="start">2015-08-14</date>
<desc><address><addrLine>TechnionIsrael Institute of TechnologyHaifa 32000Israel</addrLine>
<country key="IL"></country>
</address>
<ref type="url">http://www.cs.technion.ac.il/</ref>
</desc>
<listRelation><relation active="#struct-84142" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-84142" type="direct"><org type="institution" xml:id="struct-84142" status="VALID">          <orgName>Technion - Israel Institute of Technology [Haifa]</orgName>
          <desc>            <address>              <addrLine>Technion City, Haifa 3200003</addrLine>
              <country key="IL"></country>
            </address>
            <ref type="url">http://www1.technion.ac.il/en</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Israël</country>
</affiliation>
</author>
<author><name sortKey="Ghaffari, Mohsen" sort="Ghaffari, Mohsen" uniqKey="Ghaffari M" first="Mohsen" last="Ghaffari">Mohsen Ghaffari</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-301950" status="VALID">          <orgName>Massachusetts Institute of Technology</orgName>
          <orgName type="acronym">MIT</orgName>
          <desc>            <address>              <addrLine>77 Massachusetts Ave, Cambridge, MA 02139</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://web.mit.edu</ref>
          </desc>
        </hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Giakkoupis, George" sort="Giakkoupis, George" uniqKey="Giakkoupis G" first="George" last="Giakkoupis">George Giakkoupis</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-25733" status="OLD">          <idno type="RNSR">200718348T</idno>
          <orgName>As Scalable As Possible: foundations of large scale dynamic distributed systems</orgName>
          <orgName type="acronym">ASAP</orgName>
          <desc>            <address>              <addrLine>Campus de Beaulieu 35042 Rennes cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/equipes/asap</ref>
          </desc>
          <listRelation>            <relation active="#struct-419153" type="direct"></relation>
            <relation active="#struct-300009" type="indirect"></relation>
            <relation active="#struct-419362" type="direct"></relation>
            <relation active="#struct-105128" type="indirect"></relation>
            <relation active="#struct-172265" type="indirect"></relation>
            <relation name="UMR6074" active="#struct-441569" type="indirect"></relation>
            <relation active="#struct-247362" type="indirect"></relation>
            <relation name="- RENNES" active="#struct-301232" type="indirect"></relation>
            <relation active="#struct-301262" type="indirect"></relation>
            <relation active="#struct-105160" type="indirect"></relation>
            <relation active="#struct-411575" type="indirect"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-419153" type="direct"><org type="laboratory" xml:id="struct-419153" status="VALID"><idno type="RNSR">198018249C</idno>
<orgName>Inria Rennes – Bretagne Atlantique </orgName>
<desc><address><addrLine>Campus de beaulieu35042 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre/rennes</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-419362" type="direct"><org type="department" xml:id="struct-419362" status="OLD">          <orgName>SYSTÈMES LARGE ÉCHELLE</orgName>
          <orgName type="acronym">IRISA-D1</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">https://www.irisa.fr/fr/departements/d1-systemes-large-echelle</ref>
          </desc>
          <listRelation>            <relation active="#struct-105128" type="direct"></relation>
            <relation active="#struct-172265" type="indirect"></relation>
            <relation name="UMR6074" active="#struct-441569" type="indirect"></relation>
            <relation active="#struct-247362" type="indirect"></relation>
            <relation active="#struct-300009" type="indirect"></relation>
            <relation name="- RENNES" active="#struct-301232" type="indirect"></relation>
            <relation active="#struct-301262" type="indirect"></relation>
            <relation active="#struct-105160" type="indirect"></relation>
            <relation active="#struct-411575" type="indirect"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-105128" type="indirect"><org type="laboratory" xml:id="struct-105128" status="OLD">          <idno type="IdRef">026386909</idno>
          <idno type="ISNI">0000 0001 2298 7270</idno>
          <idno type="RNSR">200012163A</idno>
          <orgName>Institut de Recherche en Informatique et Systèmes Aléatoires</orgName>
          <orgName type="acronym">IRISA</orgName>
          <date type="start">2000</date>
          <date type="end">2016-12-31</date>
          <desc>            <address>              <addrLine>Avenue du général LeclercCampus de Beaulieu 35042 RENNES CEDEX</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.irisa.fr</ref>
          </desc>
          <listRelation>            <relation active="#struct-172265" type="direct"></relation>
            <relation name="UMR6074" active="#struct-441569" type="direct"></relation>
            <relation active="#struct-247362" type="direct"></relation>
            <relation active="#struct-300009" type="direct"></relation>
            <relation name="- RENNES" active="#struct-301232" type="direct"></relation>
            <relation active="#struct-301262" type="direct"></relation>
            <relation active="#struct-105160" type="direct"></relation>
            <relation active="#struct-411575" type="direct"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-172265" type="indirect"><org type="institution" xml:id="struct-172265" status="VALID">          <orgName>Université de Bretagne Sud</orgName>
          <orgName type="acronym">UBS</orgName>
          <desc>            <address>              <addrLine>BP 92116 - 56321 Lorient cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-ubs.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR6074" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-247362" type="indirect"><org type="institution" xml:id="struct-247362" status="VALID">          <orgName>École normale supérieure - Rennes</orgName>
          <orgName type="acronym">ENS Rennes</orgName>
          <desc>            <address>              <addrLine>Campus de Ker Lann - avenue Robert Schuman - 35170 Bruz</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.ens-rennes.fr</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="- RENNES" active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID">          <orgName>Institut National des Sciences Appliquées</orgName>
          <orgName type="acronym">INSA</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-301262" type="indirect"><org type="institution" xml:id="struct-301262" status="VALID">          <orgName>Télécom Bretagne</orgName>
          <date type="start">1977</date>
          <desc>            <address>              <addrLine>Technopôle Brest-IroiseCS 8381829238 BREST Cedex 3</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.telecom-bretagne.eu/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-105160" type="indirect"><org type="institution" xml:id="struct-105160" status="VALID">          <orgName>Université de Rennes 1</orgName>
          <orgName type="acronym">UR1</orgName>
          <desc>            <address>              <addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-rennes1.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-411575" type="indirect"><org type="institution" xml:id="struct-411575" status="VALID"><orgName>CentraleSupélec</orgName>
<desc><address><addrLine>3, rue Joliot Curie,Plateau de Moulon,91192 GIF-SUR-YVETTE Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.centralesupelec.fr</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Lorient</settlement>
<region type="region" nuts="2">Région Bretagne</region>
</placeName>
<orgName type="university">Université de Bretagne-Sud</orgName>
<orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName>
<placeName><settlement type="city">Rennes</settlement>
<region type="region" nuts="2">Région Bretagne</region>
</placeName>
<orgName type="university">Université de Rennes 1</orgName>
<orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName>
</affiliation>
</author>
<author><name sortKey="Haeupler, Bernhard" sort="Haeupler, Bernhard" uniqKey="Haeupler B" first="Bernhard" last="Haeupler">Bernhard Haeupler</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87723" status="VALID">          <orgName>Computer Science Department - Carnegie Mellon University</orgName>
          <desc>            <address>              <addrLine>Computer Science Department Carnegie Mellon University Pittsburgh, PA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cs.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-378064" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-378064" type="direct"><org type="institution" xml:id="struct-378064" status="INCOMING">          <orgName>University of Pittsburgh</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<orgName type="university">Université de Pittsburgh</orgName>
</affiliation>
</author>
<author><name sortKey="Kuhn, Fabian" sort="Kuhn, Fabian" uniqKey="Kuhn F" first="Fabian" last="Kuhn">Fabian Kuhn</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-56846" status="VALID"><orgName>Department of Computer Science [Freiburg]</orgName>
<desc><address><addrLine>Georges-Kohler-Allee 79, 79108 Freiburg, Germany</addrLine>
<country key="DE"></country>
</address>
<ref type="url">http://www.informatik.uni-freiburg.de/</ref>
</desc>
<listRelation><relation active="#struct-68615" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-68615" type="direct"><org type="institution" xml:id="struct-68615" status="VALID"><orgName>University of Freiburg [Freiburg]</orgName>
<desc><address><addrLine>Friedrichstr. 39 79098 Freiburg</addrLine>
<country key="DE"></country>
</address>
<ref type="url">http://www.uni-freiburg.de/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Allemagne</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01250519</idno>
<idno type="halId">hal-01250519</idno>
<idno type="halUri">https://hal.inria.fr/hal-01250519</idno>
<idno type="url">https://hal.inria.fr/hal-01250519</idno>
<idno type="doi">10.1137/1.9781611973730.133</idno>
<date when="2015-01-04">2015-01-04</date>
<idno type="wicri:Area/Hal/Corpus">000642</idno>
<idno type="wicri:Area/Hal/Curation">000642</idno>
<idno type="wicri:Area/Hal/Checkpoint">000173</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000173</idno>
<idno type="wicri:Area/Main/Merge">000212</idno>
<idno type="wicri:Area/Main/Curation">000212</idno>
<idno type="wicri:Area/Main/Exploration">000212</idno>
<idno type="wicri:Area/France/Extraction">000152</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Tight Bounds on Vertex Connectivity Under Vertex Sampling</title>
<author><name sortKey="Censor Hillel, Keren" sort="Censor Hillel, Keren" uniqKey="Censor Hillel K" first="Keren" last="Censor-Hillel">Keren Censor-Hillel</name>
<affiliation wicri:level="1"><hal:affiliation type="department" xml:id="struct-425640" status="VALID"><orgName>Department of Computer Science [Haifa]</orgName>
<date type="start">2015-08-14</date>
<desc><address><addrLine>TechnionIsrael Institute of TechnologyHaifa 32000Israel</addrLine>
<country key="IL"></country>
</address>
<ref type="url">http://www.cs.technion.ac.il/</ref>
</desc>
<listRelation><relation active="#struct-84142" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-84142" type="direct"><org type="institution" xml:id="struct-84142" status="VALID">          <orgName>Technion - Israel Institute of Technology [Haifa]</orgName>
          <desc>            <address>              <addrLine>Technion City, Haifa 3200003</addrLine>
              <country key="IL"></country>
            </address>
            <ref type="url">http://www1.technion.ac.il/en</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Israël</country>
</affiliation>
</author>
<author><name sortKey="Ghaffari, Mohsen" sort="Ghaffari, Mohsen" uniqKey="Ghaffari M" first="Mohsen" last="Ghaffari">Mohsen Ghaffari</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-301950" status="VALID">          <orgName>Massachusetts Institute of Technology</orgName>
          <orgName type="acronym">MIT</orgName>
          <desc>            <address>              <addrLine>77 Massachusetts Ave, Cambridge, MA 02139</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://web.mit.edu</ref>
          </desc>
        </hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Giakkoupis, George" sort="Giakkoupis, George" uniqKey="Giakkoupis G" first="George" last="Giakkoupis">George Giakkoupis</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-25733" status="OLD">          <idno type="RNSR">200718348T</idno>
          <orgName>As Scalable As Possible: foundations of large scale dynamic distributed systems</orgName>
          <orgName type="acronym">ASAP</orgName>
          <desc>            <address>              <addrLine>Campus de Beaulieu 35042 Rennes cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/equipes/asap</ref>
          </desc>
          <listRelation>            <relation active="#struct-419153" type="direct"></relation>
            <relation active="#struct-300009" type="indirect"></relation>
            <relation active="#struct-419362" type="direct"></relation>
            <relation active="#struct-105128" type="indirect"></relation>
            <relation active="#struct-172265" type="indirect"></relation>
            <relation name="UMR6074" active="#struct-441569" type="indirect"></relation>
            <relation active="#struct-247362" type="indirect"></relation>
            <relation name="- RENNES" active="#struct-301232" type="indirect"></relation>
            <relation active="#struct-301262" type="indirect"></relation>
            <relation active="#struct-105160" type="indirect"></relation>
            <relation active="#struct-411575" type="indirect"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-419153" type="direct"><org type="laboratory" xml:id="struct-419153" status="VALID"><idno type="RNSR">198018249C</idno>
<orgName>Inria Rennes – Bretagne Atlantique </orgName>
<desc><address><addrLine>Campus de beaulieu35042 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre/rennes</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-419362" type="direct"><org type="department" xml:id="struct-419362" status="OLD">          <orgName>SYSTÈMES LARGE ÉCHELLE</orgName>
          <orgName type="acronym">IRISA-D1</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">https://www.irisa.fr/fr/departements/d1-systemes-large-echelle</ref>
          </desc>
          <listRelation>            <relation active="#struct-105128" type="direct"></relation>
            <relation active="#struct-172265" type="indirect"></relation>
            <relation name="UMR6074" active="#struct-441569" type="indirect"></relation>
            <relation active="#struct-247362" type="indirect"></relation>
            <relation active="#struct-300009" type="indirect"></relation>
            <relation name="- RENNES" active="#struct-301232" type="indirect"></relation>
            <relation active="#struct-301262" type="indirect"></relation>
            <relation active="#struct-105160" type="indirect"></relation>
            <relation active="#struct-411575" type="indirect"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-105128" type="indirect"><org type="laboratory" xml:id="struct-105128" status="OLD">          <idno type="IdRef">026386909</idno>
          <idno type="ISNI">0000 0001 2298 7270</idno>
          <idno type="RNSR">200012163A</idno>
          <orgName>Institut de Recherche en Informatique et Systèmes Aléatoires</orgName>
          <orgName type="acronym">IRISA</orgName>
          <date type="start">2000</date>
          <date type="end">2016-12-31</date>
          <desc>            <address>              <addrLine>Avenue du général LeclercCampus de Beaulieu 35042 RENNES CEDEX</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.irisa.fr</ref>
          </desc>
          <listRelation>            <relation active="#struct-172265" type="direct"></relation>
            <relation name="UMR6074" active="#struct-441569" type="direct"></relation>
            <relation active="#struct-247362" type="direct"></relation>
            <relation active="#struct-300009" type="direct"></relation>
            <relation name="- RENNES" active="#struct-301232" type="direct"></relation>
            <relation active="#struct-301262" type="direct"></relation>
            <relation active="#struct-105160" type="direct"></relation>
            <relation active="#struct-411575" type="direct"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-172265" type="indirect"><org type="institution" xml:id="struct-172265" status="VALID">          <orgName>Université de Bretagne Sud</orgName>
          <orgName type="acronym">UBS</orgName>
          <desc>            <address>              <addrLine>BP 92116 - 56321 Lorient cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-ubs.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR6074" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-247362" type="indirect"><org type="institution" xml:id="struct-247362" status="VALID">          <orgName>École normale supérieure - Rennes</orgName>
          <orgName type="acronym">ENS Rennes</orgName>
          <desc>            <address>              <addrLine>Campus de Ker Lann - avenue Robert Schuman - 35170 Bruz</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.ens-rennes.fr</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="- RENNES" active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID">          <orgName>Institut National des Sciences Appliquées</orgName>
          <orgName type="acronym">INSA</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-301262" type="indirect"><org type="institution" xml:id="struct-301262" status="VALID">          <orgName>Télécom Bretagne</orgName>
          <date type="start">1977</date>
          <desc>            <address>              <addrLine>Technopôle Brest-IroiseCS 8381829238 BREST Cedex 3</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.telecom-bretagne.eu/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-105160" type="indirect"><org type="institution" xml:id="struct-105160" status="VALID">          <orgName>Université de Rennes 1</orgName>
          <orgName type="acronym">UR1</orgName>
          <desc>            <address>              <addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-rennes1.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-411575" type="indirect"><org type="institution" xml:id="struct-411575" status="VALID"><orgName>CentraleSupélec</orgName>
<desc><address><addrLine>3, rue Joliot Curie,Plateau de Moulon,91192 GIF-SUR-YVETTE Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.centralesupelec.fr</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Lorient</settlement>
<region type="region" nuts="2">Région Bretagne</region>
</placeName>
<orgName type="university">Université de Bretagne-Sud</orgName>
<orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName>
<placeName><settlement type="city">Rennes</settlement>
<region type="region" nuts="2">Région Bretagne</region>
</placeName>
<orgName type="university">Université de Rennes 1</orgName>
<orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName>
</affiliation>
</author>
<author><name sortKey="Haeupler, Bernhard" sort="Haeupler, Bernhard" uniqKey="Haeupler B" first="Bernhard" last="Haeupler">Bernhard Haeupler</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87723" status="VALID">          <orgName>Computer Science Department - Carnegie Mellon University</orgName>
          <desc>            <address>              <addrLine>Computer Science Department Carnegie Mellon University Pittsburgh, PA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cs.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-378064" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-378064" type="direct"><org type="institution" xml:id="struct-378064" status="INCOMING">          <orgName>University of Pittsburgh</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<orgName type="university">Université de Pittsburgh</orgName>
</affiliation>
</author>
<author><name sortKey="Kuhn, Fabian" sort="Kuhn, Fabian" uniqKey="Kuhn F" first="Fabian" last="Kuhn">Fabian Kuhn</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-56846" status="VALID"><orgName>Department of Computer Science [Freiburg]</orgName>
<desc><address><addrLine>Georges-Kohler-Allee 79, 79108 Freiburg, Germany</addrLine>
<country key="DE"></country>
</address>
<ref type="url">http://www.informatik.uni-freiburg.de/</ref>
</desc>
<listRelation><relation active="#struct-68615" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-68615" type="direct"><org type="institution" xml:id="struct-68615" status="VALID"><orgName>University of Freiburg [Freiburg]</orgName>
<desc><address><addrLine>Friedrichstr. 39 79098 Freiburg</addrLine>
<country key="DE"></country>
</address>
<ref type="url">http://www.uni-freiburg.de/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Allemagne</country>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1137/1.9781611973730.133</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">A fundamental result by Karger (SODA 1994) states that for any λ-edge-connected graph with n nodes, independently sampling each edge with probability p = Ω(log n/λ) results in a graph that has edge connectivity Ω(λp), with high probability. This paper proves the analogous result for vertex connectivity, when sampling vertices. We show that for any k-vertex-connected graph G with n nodes, if each node is independently sampled with probability p = Ω(log n/k), then the subgraph induced by the sampled nodes has vertex connectivity Ω(kp^2), with high probability. This bound improves upon the recent results of Censor-Hillel et al. (SODA 2014), and is existentially optimal.</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
<li>France</li>
<li>Israël</li>
<li>États-Unis</li>
</country>
<region><li>Pennsylvanie</li>
<li>Région Bretagne</li>
</region>
<settlement><li>Lorient</li>
<li>Pittsburgh</li>
<li>Rennes</li>
</settlement>
<orgName><li>Université de Bretagne-Sud</li>
<li>Université de Pittsburgh</li>
<li>Université de Rennes 1</li>
<li>Université européenne de Bretagne</li>
</orgName>
</list>
<tree><country name="Israël"><noRegion><name sortKey="Censor Hillel, Keren" sort="Censor Hillel, Keren" uniqKey="Censor Hillel K" first="Keren" last="Censor-Hillel">Keren Censor-Hillel</name>
</noRegion>
</country>
<country name="États-Unis"><noRegion><name sortKey="Ghaffari, Mohsen" sort="Ghaffari, Mohsen" uniqKey="Ghaffari M" first="Mohsen" last="Ghaffari">Mohsen Ghaffari</name>
</noRegion>
<name sortKey="Haeupler, Bernhard" sort="Haeupler, Bernhard" uniqKey="Haeupler B" first="Bernhard" last="Haeupler">Bernhard Haeupler</name>
</country>
<country name="France"><region name="Région Bretagne"><name sortKey="Giakkoupis, George" sort="Giakkoupis, George" uniqKey="Giakkoupis G" first="George" last="Giakkoupis">George Giakkoupis</name>
</region>
</country>
<country name="Allemagne"><noRegion><name sortKey="Kuhn, Fabian" sort="Kuhn, Fabian" uniqKey="Kuhn F" first="Fabian" last="Kuhn">Fabian Kuhn</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/France/Analysis

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000152 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000152 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    France
   |étape=   Analysis
   |type=    RBID
   |clé=     Hal:hal-01250519
   |texte=   Tight Bounds on Vertex Connectivity Under Vertex Sampling
}}

This area was generated with Dilib version V0.6.38.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021

	Serveur d'exploration sur Pittsburgh
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur Pittsburgh

Tight Bounds on Vertex Connectivity Under Vertex Sampling

Tight Bounds on Vertex Connectivity Under Vertex Sampling

Source :

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri